﻿//84. 柱状图中最大的矩形
//给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
//求在该柱状图中，能够勾勒出来的矩形的最大面积。


class Solution {
public:
    int largestRectangleArea(vector<int>& heights)
    {
        heights.push_back(0);
        heights.insert(heights.begin(), 0);
        int n = heights.size();
        int ans = 0;
        stack<int> sta;
        for (int i = 0; i < n; i++)
        {
            //单调递增
            while (!sta.empty() && heights[i] < heights[sta.top()])
            {
                int h = heights[sta.top()];
                sta.pop();
                ans = max(ans, (i - sta.top() - 1) * h);
            }
            sta.push(i);
        }
        return ans;
    }
};